/*
 * @lc app=leetcode.cn id=464 lang=typescript
 *
 * [464] 我能赢吗
 */

// @lc code=start

function dfs(mask: number, n: number, total: number, hash: Map<number, boolean>): boolean {
  // 记忆化
  if (hash.has(mask)) return hash.get(mask);
  for (let i = 1; i <= n; i++) {
    if (mask & (1 << i)) continue;
    if (i >= total) return true;
    // 我选择完了，递归去计算对方的结果
    // 如果我要赢，那对方必须输才可以
    if (!dfs(mask | (1 << i), n, total - i, hash)) {
      hash.set(mask, true);
      return true;
    }
  }
  hash.set(mask, false);
  return false;
}

function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
  // 如果maxChoosableInteger累加和小于desiredTotal，第一个肯定输
  if (((maxChoosableInteger + 1) * maxChoosableInteger) / 2 < desiredTotal) return false;
  // 使用位操作记录用过的数字
  const mask = 0;
  // 记忆化，mask自变量，当作key
  const hash: Map<number, boolean> = new Map();
  return dfs(mask, maxChoosableInteger, desiredTotal, hash);
}
// @lc code=end
